/*
 * @Author: yuzezhong 
 * @Date: 2019-06-17 14:40:00 
 * @Last Modified by: yuzezhong
 * @Last Modified time: 2019-06-17 16:40:35
 */
#include <iostream>
#include <vector>

using namespace std;

/**
 * @brief 选择出第k大的数，算法要求传入引用
 * 
 * @param list 
 * @param start　起始位置 
 * @param end 结束位置
 * @param k 第k大
 * @return int 第k大的数
 */

int select_kth(vector<int> &list, int start, int end, int k)
{
    if (start == end)
        return list.at(start);
    int pivot = list.at(start);
    int left = start;
    int right = end;
    while (left != right)
    {
        while (list.at(right) >= pivot && left < right)
            right--;
        list.at(left) = list.at(right);
        while (list.at(left) < pivot && left < right)
            left++;
        list.at(right) = list.at(left);
    }
    list.at(left) = pivot;

    cout << "left = " << left << endl;
    cout << "k = " << k << endl;
    if (k - 1 > left)
    {
        cout << "k - 1 > left" << endl;
        select_kth(list, left + 1, end, k - 1 - left);
    }
    else if (k - 1 < left)
    {
        cout << "k - 1 < left" << endl;
        select_kth(list, start, left, k);
    }
    else
        return list.at(k - 1);
}

int main()
{
    vector<int> list(10);
    srand(time(0));
    for (int i = 0; i < 10; i++)
    {
        list.at(i) = rand() % 10 + 1;
        list.at(i) += rand() % 5 + 1;
    }

    for (auto &&i : list)
    {
        cout << i << ", ";
    }
    cout << endl;

    int k = 4;
    int kth_value = select_kth(list, 0, list.size() - 1, k);
    cout << k << "th value is " << kth_value << endl;
    return 0;
}
